Divisor Counting Function

Often this function is instead denoted by $\tau$.

Proof

This is a counting problem. If $n=p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}$ then factors are of the form $p_1^{{\beta }_1}\dots p_k^{{\beta }_k}$ where ${\beta }_i\le {\beta }_j$ as per divisibility from unique factorisations. Each possible value of each ${\beta }_i$ defines a unique factor and for each $i$, ${\beta }_i\in \{0,\dots ,{\alpha }_i\}$ which means there are ${\alpha }_i+1$ possible values.

Hence we have

We can also express the divisor counting function as a Dirichlet convolution.

Proof

Let $n=p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}$ and $m=q_1^{{\beta }_1}\dots q_s^{{\beta }_s}$. If $gcd(m,n)=1$, then $p_i\ne q_j$ for all $i,j$. Therefore $nm=p_1^{{\alpha }_1}\dots p_k^{{\alpha }_k}{q}_1^{{\beta }_1}\dots q_s^{{\beta }_s}$ is the unique factorisation into a product of primes without duplicate primes.

As such we have